#include "Quadtree.h"
#include "Object.h"
#include "Player.h"
namespace Advanced2D
{

	QuadTree::QuadTree(int w,int h)
	{
		_mapWidth=w;
		_mapHeight=h;
		_pRoot=new QuadNode(0,0,_mapWidth,_mapHeight);
		//_count=0;
	}
	void QuadTree::Add(QuadNode *root,Object *Ob)
	{	
		if(root!=NULL)
		{
			//0: Add ....1: Left_Top..... 2: Right_Top....... 3: Left_Bottom...... 4: Right_Bottom
			int result=0;//add here

			int objWidth	=	Ob->getObjectRect().right - Ob->getObjectRect().left;
			int objHeight	=	Ob->getObjectRect().bottom - Ob->getObjectRect().top;

			int rectWidth	=	root->_rect->right - root->_rect->left; 
			int rectHeight	=	root->_rect->bottom - root->_rect->top;

			int rectWidthNew=	(root->_rect->right + root->_rect->left)/2; //divide RECT root to quad RECT
			int rectHeightNew=	(root->_rect->bottom + root->_rect->top)/2;

			if((objWidth*objHeight > rectWidth*rectHeight/4)/*kiem tra dien tich co lon hon 1/4 dien tich roof ko*/ 
				|| (rectWidthNew > Ob->getObjectRect().left && rectWidthNew <= Ob->getObjectRect().right)||
				(rectHeightNew > Ob->getObjectRect().top && rectHeightNew <= Ob->getObjectRect().bottom))
				result=0;//Kiem tra xem objet nam o hon 1/4 cua root thi tra ve khong
			else
			{
				if(Ob->getObjectRect().left >= root->_rect->left &&
					Ob->getObjectRect().left < rectWidthNew &&
					Ob->getObjectRect().top >= root->_rect->top &&
					Ob->getObjectRect().top < rectHeightNew)//Left_Top
					result =1;
				else 
					if(Ob->getObjectRect().left < root->_rect->right &&
						Ob->getObjectRect().left >= rectWidthNew &&
						Ob->getObjectRect().top >= root->_rect->top &&
						Ob->getObjectRect().top < rectHeightNew)//Right_Top
						result =2;
					else 
						if(Ob->getObjectRect().left >= root->_rect->left &&
							Ob->getObjectRect().left < rectWidthNew &&
							Ob->getObjectRect().top >= rectHeightNew &&
							Ob->getObjectRect().top < root->_rect->bottom)//Left_Bottom
							result=3;
						else//Right_Bottom
							result=4;
			}

			if(result==0)//Add here
			{
				root->listObj.push_back(Ob);
				_count++; 
			}
			else
			{
				if(rectWidth/2 > LIM_W_H && rectHeight/2 > LIM_W_H)
				{
					switch(result)
					{
					case 1://Left_Top
						if(root->LT==NULL)
							root->LT=new QuadNode(root->_rect->left,root->_rect->top,rectWidth/2,rectHeight/2);
						Add(root->LT,Ob);
						break;
					case 2://Right_Top
						if(root->RT==NULL)
							root->RT=new QuadNode(rectWidthNew,root->_rect->top,rectWidth/2,rectHeight/2);
						Add(root->RT,Ob);
						break;
					case 3://Left_Bottom
						if(root->LB==NULL)
							root->LB=new QuadNode(root->_rect->left,rectHeightNew,rectWidth/2,rectHeight/2);
						Add(root->LB,Ob);
						break;
					case 4://Right_Bottom
						if(root->RB==NULL)
							root->RB=new QuadNode(rectWidthNew,rectHeightNew,rectWidth/2,rectHeight/2);
						Add(root->RB,Ob);
						break;
					}
				}
			}
		}
	}

	bool QuadTree::CheckPointInRECT(int x,int y,RECT rect)
	{
		if(x >= rect.left && x <= rect.right && y >= rect.top && y <= rect.bottom)
			return true;
		return false;
	}

	bool QuadTree::CheckRECTInRECT(RECT r,RECT rect)
	{
		if(CheckPointInRECT(r.left,r.top,rect)
			||CheckPointInRECT(r.right,r.top,rect)
			||CheckPointInRECT(r.left,r.bottom,rect)
			||CheckPointInRECT(r.right,r.bottom,rect)
			||(rect.top<=r.top&&rect.bottom>=r.bottom&&r.left<=rect.left&&r.right>=rect.right))
		{
			return true;
		}
		return false;
	}
	void QuadTree::GetObjInRec(QuadNode* root,RECT Screen,vector<Object*> &result)
	{
		for(int i=0;i<root->listObj.size();i++)
			if(CheckRECTInRECT(root->listObj[i]->getObjectRect(),Screen)||CheckRECTInRECT(Screen,root->listObj[i]->getObjectRect()))//active items on camera
			{
				result.push_back(root->listObj[i]);
			}
			if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,Screen)||CheckRECTInRECT(Screen,*root->LT->_rect)))
				GetObjInRec(root->LT,Screen,result);
			if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,Screen)||CheckRECTInRECT(Screen,*root->RT->_rect)))
				GetObjInRec(root->RT,Screen,result);
			if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,Screen)||CheckRECTInRECT(Screen,*root->LB->_rect)))
				GetObjInRec(root->LB,Screen,result);
			if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,Screen)||CheckRECTInRECT(Screen,*root->RB->_rect)))
				GetObjInRec(root->RB,Screen,result);
	}
	void QuadTree::DrawObjects(RECT Screen)
	{
		vector<Object*> total;
		this->GetAllObj(_pRoot,total);

		vector<Object*> result;
		//vector<Object*> allObjet;
		//GetAllObj(_pRoot,allObjet);
		GetObjInRec(_pRoot,Screen,result);
		for (int i=0; i<result.size();i++)
		{
			result[i]->draw(Screen);
		}
	}
	//Object* QuadTree::CheckCollision(QuadNode *root,RECT r,int Seq)
	//{	
	//	for(int i=0;i<root->listObj.size();i++)
	//		if(root->listObj[i]->_typeObj!=-1//Day la nhung Object chi dung de trang tri
	//			&&root->listObj[i]->_status!=2//Chua chet
	//			&&root->listObj[i]->_id!=Seq
	//			&&(CheckRECTInRECT(*root->listObj[i]->getObjectRect(),r)||CheckRECTInRECT(r,*root->listObj[i]->getObjectRect())))
	//			return root->listObj[i];//Dung do
	//	if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->LT,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->RT,r,Seq);
	//		if(ob!=NULL)	
	//			return ob;
	//	}
	//	if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->LB,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->RB,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	return NULL;
	//}

	//Object* QuadTree::CheckCollision(QuadNode *root,RECT r,int Seq)
	//{	
	//	for(int i=0;i<root->listObj.size();i++)
	//		if(root->listObj[i]->_typeObj!=-1//Day la nhung Object chi dung de trang tri
	//			&&root->listObj[i]->_status!=2//Chua chet
	//			&&root->listObj[i]->_id!=Seq
	//			&&(CheckRECTInRECT(*root->listObj[i]->getObjectRect(),r)||CheckRECTInRECT(r,*root->listObj[i]->getObjectRect())))
	//			return root->listObj[i];//Dung do
	//	if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->LT,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->RT,r,Seq);
	//		if(ob!=NULL)	
	//			return ob;
	//	}
	//	if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->LB,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
	//	{
	//		Object *ob=CheckCollision(root->RB,r,Seq);
	//		if(ob!=NULL)
	//			return ob;
	//	}
	//	return NULL;
	//}

	void QuadTree::CheckCollision(QuadNode *root,RECT r,vector<Object*>&result)
	{	
		for(int i=0;i<root->listObj.size();i++)
			if(//Day la nhung Object chi dung de trang tri
				root->listObj[i]->getAlive()==true//Chua chet
				&&(CheckRECTInRECT(root->listObj[i]->getObjectRect(),r)||CheckRECTInRECT(r,root->listObj[i]->getObjectRect())))
			{
				result.push_back(root->listObj[i]);
			}
			if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
			{
				CheckCollision(root->LT,r,result);

			}
			if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
			{
				CheckCollision(root->RT,r,result);

			}
			if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
			{
				CheckCollision(root->LB,r,result);

			}
			if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
			{
				CheckCollision(root->RB,r,result);
			}

	}

	//void QuadTree::CheckCollision(QuadNode *root,RECT r,int Seq,vector<Object*>&result)
	//{	
	//	for(int i=0;i<root->listObj.size();i++)
	//		if(root->listObj[i]->_typeObj!=-1//Day la nhung Object chi dung de trang tri
	//			&&root->listObj[i]->_status!=2//Chua chet
	//			&&root->listObj[i]->_id!=Seq
	//			&&(CheckRECTInRECT(*root->listObj[i]->getObjectRect(),r)||CheckRECTInRECT(r,*root->listObj[i]->getObjectRect())))
	//		{
	//			//Object* obj= root->listObj[i];
	//			result.push_back(root->listObj[i]);
	//		}
	//		if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,r)||CheckRECTInRECT(r,*root->LT->_rect)))
	//		{
	//			CheckCollision(root->LT,r,Seq,result);

	//		}
	//		if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,r)||CheckRECTInRECT(r,*root->RT->_rect)))
	//		{
	//			CheckCollision(root->RT,r,Seq,result);

	//		}
	//		if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,r)||CheckRECTInRECT(r,*root->LB->_rect)))
	//		{
	//			CheckCollision(root->LB,r,Seq,result);

	//		}
	//		if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,r)||CheckRECTInRECT(r,*root->RB->_rect)))
	//		{
	//			CheckCollision(root->RB,r,Seq,result);
	//		}

	//}
	//bool QuadTree::IsOnObject(RECT *rect,int Seq)//duoi chan object la object khac hay la khoang trong
	//{
	//	RECT r;
	//	r.left=rect->left;r.right=rect->right;
	//	r.top=rect->top+1;r.bottom=rect->bottom+1;
	//	vector<Object*> result;
	//	CheckCollision(_pRoot,r,Seq,result);
	//	for(int i=0;i<result.size();i++)
	//	{
	//		Object* obj=result[i];
	//		if(obj->_typeObj==0)
	//			return true;
	//	}

	//	return false;
	//}
	void QuadTree::UpdatePosition(QuadNode *root,bool& OK)
	{
		//vector<Object*> okconde;
		//GetAllObj(_pRoot,okconde);

		if (root->LT == NULL && root->LB==NULL && root->RB==NULL && root->RT==NULL)
		{
			return;
		}
		vector<Object*>::iterator begin, end;
		begin=root->listObj.begin();
		end=root->listObj.end();

		while(begin!=end)
		{
			Object *Ob= *begin;

			if(Ob->IsMoving())
			{	
				if(Ob->IsMoving())
				{
					root->listObj.erase(begin);
					this->Add(_pRoot,Ob);
					OK=true;
				}
			}
			else
				begin++;
		}
		if(root->LT!=NULL)
			UpdatePosition(root->LT,OK);
		if(root->RT!=NULL)
			UpdatePosition(root->RT,OK);
		if(root->LB!=NULL)
			UpdatePosition(root->LB,OK);
		if(root->RB!=NULL)
			UpdatePosition(root->RB,OK);
	}

	QuadTree::~QuadTree(void)
	{
	}

	void QuadTree::GetAllObj(QuadNode *root,vector<Object*> &result)
	{

		for(int i=0;i<root->listObj.size();i++)
			result.push_back(root->listObj[i]);

		if(root->LT!=NULL)
			GetAllObj(root->LT,result);

		if(root->LB!=NULL)
			GetAllObj(root->LB,result);

		if(root->RT!=NULL)
			GetAllObj(root->RT,result);

		if(root->RB!=NULL)
			GetAllObj(root->RB,result);
	}

	void QuadTree::RemoveAll(QuadNode *root)
	{
		if (root!=NULL)
		{
			root->listObj.clear();
		}
		if (root->LB!=NULL)
			RemoveAll(root->LB);
		if (root->LT!=NULL)
			RemoveAll(root->LB);
		if (root->RB!=NULL)
			RemoveAll(root->LB);
		if (root->RT!=NULL)
			RemoveAll(root->LB);
	}
}